import java.util.Stack;

/*
    1019. 链表中的下一个更大节点
    可以用list来放数据，这样可以少一次循环
 */

public class NextLargerNodes {

    public int[] nextLargerNodes(ListNode head) {
        int n = 0;
        ListNode temp = head;
        int i = 0;
        Stack<Integer> stack = new Stack<>();
        while (temp != null) {
            n++;
            temp = temp.next;
        }
        int[] ans = new int[n];
        int[] temp1 = new int[n];
        temp = head;
        while (temp != null) {
            temp1[i++] = temp.val;
            temp = temp.next;
        }
        for (int j = 0; j < temp1.length; j++) {
            while (!stack.isEmpty() && temp1[stack.peek()] < temp1[j]) {
                Integer pop = stack.pop();
                ans[pop] = temp1[j];
            }
            stack.push(j);
        }
        return ans;
    }
}
